---
title: "5、递增三元组"
created: 2025-11-28
tags:
  - 算法
---

# 5、递增三元组

## 题目 [递增三元组](https://www.lanqiao.cn/paper/3848/problem/172/)

![[image-1f198130.png]]

## 思路分析

![[image-d23c36f0.png]]

![[image-a2b342b9.png]]

1、三个排序

2、对于每一个b 找比他小的a的数量 比他大的c的数量 相乘

3、相加

靠 这题忘了开LL 少过两个案例 逻辑想完了后要多检查一下这些东西啊

嘶 好像也检查不到 要不每次直接开大点？一般也不会卡这点空间？？？

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[N],b[N],c[N];

int n;

int main()

{

	cin>>n;

	for(int i=0;i<n;i++)	cin>>a[i];

	for(int i=0;i<n;i++)	cin>>b[i];

	for(int i=0;i<n;i++)	cin>>c[i];

	sort(a,a+n);sort(b,b+n);sort(c,c+n);

	LL sum=0;

	for(int i=0;i<n;i++){

		int x=b[i];

		int l=0,r=n;

		while(l<r){

			int m=l+r>>1;

			if(a[m]>=x)//找到第一个不小于x的数 它的下标-0就是小于x的数量

				r=m;

			else

				l=m+1;

		}

		int cnt_a=r;

		l=0,r=n;

		while(l<r){

			int m=l+r>>1;

			if(c[m]>x)//找到第一个大于x的数 n-r就是大于x的数量

				r=m;

			else

				l=m+1;

		}

		LL cnt_b=n-r;

		sum+=cnt_a*cnt_b;

	}

	cout<<sum;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[4、测试次数|4、测试次数]] 🏠 [[00-刷题理模型]] ➡️ [[6、日志统计|6、日志统计]]